home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1994 / MacHack 1994.toast / MacHack™ 1987-1994 / MacHack™ '87 / Xref.folder / xref.c next >
Encoding:
C/C++ Source or Header  |  1987-01-08  |  16.8 KB  |  578 lines  |  [TEXT/Anon]
  1. /********************************************************************/
  2. /*        Program: XRef.c                                                   */
  3. /*        This program comes from 'The C Programming Tutor'            */
  4. /*        by Leon A. Wortman and Thomas O. Sidebottom.                   */
  5. /*        This program has typical UNIX interface and yields             */ 
  6. /*        a numbered listing and an alphabetized cross                   */
  7. /*        reference listing with all reference line numbers              */
  8. /*        of all C identifiers used in the program.                      */
  9. /*                                                                       */
  10. /*        Modified for the Alpha Micro C by John Pence                   */
  11. /* compiles as a tool under MPW-Macintosh programers workshop also  */
  12. /********************************************************************/
  13.  
  14. /***********************************************************/
  15. /*             Include Files                                   */
  16. /***********************************************************/
  17. #include    <stdio.h>
  18. #include    <ctype.h>
  19.  
  20. /***********************************************************/
  21. /*        definitions                                            */
  22. /***********************************************************/
  23. #define CR            13
  24. #define    BOOL            int
  25. #define    DQUOTE            '"'
  26. #define    EQUALS            0
  27. #define    FALSE            0
  28. #define    FIRSTGREATER    1
  29. #define    FIRSTLESS        -1
  30. #define    HTSIZE            1009        /* Must be a prime number */
  31. #define    MAXSTRLEN        255
  32. #define    MAXWORDSIZE        20
  33. #define    SLASH            '/'
  34. #define    SQUOTE            '\''
  35. #define STAR            '*'
  36. #define    TRUE            1
  37. #define    VOID            int
  38.  
  39. /***********************************************************/
  40. /*            code macros                                       */
  41. /***********************************************************/
  42. #define    PutBack(Ch)    {PutBackChar = Ch; }
  43. #define    GenerateNewIndex( x, y )    ( ( (x + y * y) % HTSIZE))
  44.  
  45. /***********************************************************/
  46. /*            typedefs                                         */
  47. /***********************************************************/
  48. typedef    struct    rType    {
  49.     int    Reference ;            /* line number */
  50.     struct    rType    *Link;    /* link to next reference */
  51. }
  52. RefType, *RefPtr ;
  53.  
  54. typedef    struct    tType    {
  55.     char    *Value ;    /* pointer to token */
  56.     RefPtr    OccurList ;    /* line number list */
  57. }
  58. TokenType, *TokenPtr ;
  59.  
  60. /***********************************************************/
  61. /*                external functions                              */
  62. /***********************************************************/
  63. extern    char    *malloc() ;
  64. extern    RefPtr    MakeOccurrence() ;
  65.  
  66. /***********************************************************/
  67. /*                global variables                              */
  68. /***********************************************************/
  69. int            CurLineNo = 1 ;            /* Line being read */
  70. char        OldChar, CurChar = '\0' ;
  71. TokenType    HashTable[HTSIZE] ;
  72. int            PutBackChar = '\0' ;    /* Character put back after input */
  73.  
  74. /***********************************************************/
  75. /*                *** MAIN ***                                  */
  76. /***********************************************************/
  77. main( argc, argv )
  78. int        argc;
  79. char    **argv  ;
  80. {        /* main */
  81.     int        Counter ;
  82.     char    CurToken [MAXSTRLEN] ;
  83.     FILE    *InFile ;
  84.     /* There must be at least one command-line option.
  85.      */
  86.     if ( argc < 2 ) {
  87.         fprintf(stderr, "USAGE: xref filename<cr>\n") ;
  88.         exit(0);
  89.     }
  90.     
  91.     if (!(InFile = fopen(argv[1],"r"))) {
  92.         fprintf(stderr,"Can't open input file \"%s\".\n",argv[1]) ;
  93.         exit(0) ;
  94.     }
  95.     
  96.     /* Initialize the Hash Table.
  97.      */
  98.     for (Counter = 0; Counter < HTSIZE ; Counter++ ) {
  99.         HashTable[Counter].Value = NULL ;
  100.         HashTable[Counter].OccurList = NULL ;
  101.     }
  102.     
  103.     /* Write the first line number to the output stream.
  104.      */
  105.     printf("\n%4d    ",CurLineNo) ;
  106.     
  107.     /* Read and store each Token.
  108.      */
  109.     while (GetNxtToken(CurToken,InFile)) {
  110.         if (InsertToken(CurToken)) {
  111.             fprintf(stderr,"Hash Table size exceeded.\n") ;
  112.             break ;
  113.         }        /* if */
  114.     }        /* while */
  115.     printf("*** END OF FILE ***\n\n") ;
  116.     
  117.     /* Sort the Tokens alphabetically
  118.      */
  119.     SortTokens(HTSIZE) ;
  120.     
  121.     PrintTable() ;
  122. }    /* main */
  123.  
  124. /*==========================================================*/
  125. /*        *** AddOccurrence() ***                                */
  126. /*==========================================================*/
  127. VOID    AddOccurrence(HeadPtr)
  128. RefPtr    HeadPtr ;
  129. /* AddOccurrence adds a new line to the
  130.  * end of the list that HeadPtr begins.
  131.  */
  132. {    /* AddOccurrence */
  133.     RefPtr    CurPtr ;
  134.     RefPtr    NewPtr ;
  135.     
  136.     /* Find the end of the list by starting at
  137.      * the begginning and advancing through the list
  138.      * until we find the end.
  139.      */
  140.     for (CurPtr = HeadPtr; CurPtr->Link != NULL;
  141.             CurPtr = CurPtr->Link)
  142.         ;
  143.         
  144.     CurPtr->Link = NewPtr = (RefPtr)malloc(sizeof(RefType)) ;
  145.     if (NewPtr == NULL) {
  146.         fprintf(stderr,"Out of Memory in AddOccurrence.\0") ;
  147.         exit(0) ;
  148.     }
  149.     NewPtr->Reference = CurLineNo ;
  150.     NewPtr->Link = (RefPtr)NULL ;
  151. }    /* AddOccurrence */
  152.  
  153. /*==========================================================*/
  154. /*        *** Copy() ***                                        */
  155. /*==========================================================*/    
  156. char    *Copy(OldString)
  157. char    *OldString ;
  158. /* Copy makes a copy of OldString and returns the address of
  159.  * the copy.
  160.  */
  161. {        /* Copy */
  162.     char        *NewString ;
  163.     
  164.     /* Allocate a string able to hold the length
  165.      * of the string plus one for the terminator.
  166.      */
  167.     NewString = malloc(strlen(OldString) +1) ;
  168.     
  169.     /* Copy the string and return a pointer to it.
  170.      */
  171.      strcpy(NewString,OldString) ;
  172.      return(NewString) ;
  173. }        /* Copy */
  174.  
  175. /*==========================================================*/
  176. /*        *** GetNxtChar() ***                                */
  177. /*==========================================================*/
  178. int        GetNxtChar(InputFile)
  179. FILE    *InputFile ;
  180. /* GetNxtChar returns the next non-comment
  181.  * a non-string character from InputFile.
  182.  *
  183.  * At least one character is read from InputFile. If
  184.  * the character could start a comment, the next character
  185.  * is checked. If the slash-star of a comment
  186.  * is read, the reading of characters continues until the end
  187.  * of the comment is found. If a single or double quote
  188.  * is read, the reading of characters continues until
  189.  * the closing mark is found. When EOF is encountered,
  190.  * EOF is returned. GetNxtChar therefore never returns
  191.  * characters inside comments or quotes.
  192.  */
  193. {    /* GetNxtChar */
  194.     int        CheckChar ;
  195.     int        NewChar ;
  196.     int        TempChar ;
  197.     
  198.     /* If end-of-file is found, return immediately.
  199.      */
  200.     if ((NewChar = GetRawChar(InputFile)) == EOF)
  201.         return (EOF) ;
  202.         
  203.     /* If a single or double quote is found, process the string.
  204.      */
  205.     if (NewChar == SQUOTE || NewChar == DQUOTE) {
  206.         CheckChar = NewChar ;
  207.         /* Continue reading until the matching quote character
  208.          * is found.
  209.          */
  210.         do {
  211.             if ((NewChar = GetRawChar(InputFile)) == '\\') {
  212.                 /* If LITERAL QUOTE is found in string;
  213.                  * ignore it.
  214.                  */
  215.                 while (((NewChar = GetRawChar(InputFile)) != EOF) &&
  216.                         (NewChar == DQUOTE)) ;
  217.                     continue;
  218.             }
  219.         } while (NewChar != CheckChar && NewChar != EOF) ;
  220.         /* The terminating character has now been read.
  221.          * Read one more and return it.
  222.          */
  223.         NewChar = GetRawChar(InputFile) ;
  224.     }
  225.     
  226.     /* Next, handle comment processing. If SLASH is read,
  227.      * check to see if the next character is a STAR. If it is,
  228.      * continue reading until the next STAR-SLASH is found.
  229.      */
  230.     else if (NewChar == SLASH) {
  231.         if ((TempChar = GetRawChar(InputFile)) != STAR) {
  232.             /* Not a comment; putback the character.
  233.              */
  234.             PutBack(TempChar) ;
  235.         }
  236.         else
  237.             /* Here's a comment. Search for the end.
  238.              */
  239.             do {
  240.                 /* Read characters until a STAR is found.
  241.                  */
  242.                 if (((NewChar = GetRawChar(InputFile)) == STAR) &&
  243.                     NewChar != EOF) {
  244.                     while (((NewChar = GetRawChar(InputFile)) == STAR) &&
  245.                             NewChar != EOF) ;
  246.                     if (NewChar == EOF)
  247.                             break;
  248.                 }
  249.             } while (NewChar != SLASH && NewChar != EOF) ;        /* do */
  250.         NewChar = GetRawChar(InputFile) ;
  251.     }        /* else if */
  252.     return (NewChar) ;
  253. }        /* GetNxtChar */
  254.  
  255. /*==========================================================*/
  256. /*        *** GetNxtToken() ***                                */
  257. /*==========================================================*/
  258. BOOL    GetNxtToken(Buffer, InputFile)
  259. char    *Buffer ;
  260. FILE    *InputFile ;
  261. /* GetNxtToken returns in Buffer, the next valid C token in the 
  262.  * program.
  263.  */
  264. {        /* GetNxtToken */
  265.     int        CurChar, OldChar ;
  266.     
  267.     /* Read the characters from the InputFile until starting letter is
  268.      * found. Stop when a valid letter or end-of-file is found.
  269.      */
  270.     while (!IsStartingLetter(CurChar = GetNxtChar(InputFile), OldChar) &&
  271.             CurChar != EOF)
  272.         OldChar = CurChar;
  273.     
  274.     /* Read the first character.
  275.      */
  276.     *Buffer++ = CurChar ;
  277.     
  278.     /* Read and accumulate characters in buffer while they are
  279.      * valid letters for a token.
  280.      */
  281.     while (IsTokenLetter(CurChar = GetNxtChar(InputFile)) &&
  282.             CurChar != EOF)
  283.         *Buffer++ = CurChar ;
  284.     
  285.     /* Put back the last character we read.
  286.      */
  287.     if (CurChar != EOF)
  288.         PutBack(CurChar) ;
  289.         
  290.     /* Terminate the Token.
  291.      */
  292.     *Buffer = '\0' ;
  293.     
  294.     /* Return end-of-file status.
  295.      */
  296.     return ((CurChar == EOF) ? FALSE : TRUE) ;
  297. }        /* GetNxtToken */
  298.  
  299. /*==========================================================*/
  300. /*        *** GetRawChar() ***                                */
  301. /*==========================================================*/
  302. int        GetRawChar(InputFile)
  303. FILE    *InputFile ;
  304. /* GetRawChar reads the next character fromn the InputFile and
  305.  * returns it. If a newline is read, it increments
  306.  * CurLineNo. If end-of-file is read, it returns EOF.
  307.  */
  308. {        /* GetRawChar */
  309.     int        NextChar ;
  310.     /* Check PutBackChar to see if the next character has
  311.      * already been read. If so, process it and set PutBackChar
  312.      * to the NULL character.
  313.      */
  314.     if (PutBackChar != '\0') {
  315.         NextChar = PutBackChar ;
  316.         PutBackChar = '\0' ;
  317.     }
  318.     else {
  319.         /* Echo the character read to the output stream.
  320.          * If a CR is read, increment the line count.
  321.          */
  322.         if ((NextChar = getc(InputFile)) == '\n')
  323.             printf("\n%4d    ", ++CurLineNo) ;
  324.         else {
  325.             if (NextChar != EOF)
  326.                 putchar(NextChar) ;
  327.         }
  328.     }
  329.     
  330.     if (NextChar == EOF)
  331.         return (EOF) ;
  332.         
  333.     return (NextChar) ;
  334. }        /* GetRawChar */
  335.  
  336. /*==========================================================*/
  337. /*        *** Hash() ***                                        */
  338. /*==========================================================*/
  339. int     Hash(Word)
  340. char    *Word ;
  341. /* Hash returns the HTIndex of the Word passed, or an
  342.  * appropriate HTIndex for the Word. If HashTable is
  343.  * full, Hash returns -1.
  344.  */
  345. {        /* Hash */
  346.     int        HTIndex ;
  347.     int        IdLen ;
  348.     int        InitHTIndex ;
  349.     int        ProbeCounter = 0 ;
  350.     
  351.     IdLen = strlen(Word) ;
  352.     if (IdLen == 0)
  353.         printf("Hash: Word of no length\n") ;        
  354.     HTIndex = InitHTIndex = TransformId(Word) ;
  355.     if (HashTable[HTIndex].Value == NULL)
  356.         ;        /* no-op - We've got it. */
  357.     else        /* Have we found the correct index? */
  358.     
  359.     if (strcmp(Word,HashTable[HTIndex].Value) == EQUALS)
  360.         ;        /* DONE: A direct hit! */
  361.         
  362.     else        /* Collision -- generate indexes */
  363.         for (ProbeCounter=0; ProbeCounter<(HTSIZE / 2);
  364.         ProbeCounter++) {
  365.             HTIndex = GenerateNewIndex(InitHTIndex, ProbeCounter) ;
  366.             if (HashTable[HTIndex].Value == NULL)
  367.                 break ; /* We've got it ! */
  368.             else if (strcmp(Word,HashTable[HTIndex].Value)
  369.             == EQUALS)
  370.                 break ; /* We've got it ! */
  371.         }
  372.         
  373.     if (ProbeCounter >= (HTSIZE / 2))
  374.         return(-1) ;
  375.     return(HTIndex) ;
  376. }        /* Hash */
  377.     
  378. /*==========================================================*/
  379. /*        *** InsertToken() ***                                */
  380. /*==========================================================*/
  381. BOOL     InsertToken(Token)
  382. char    *Token ;
  383. /* Inserts the Token into the hash table if it is new. If
  384.  * the Token is previously known, it adds the line number
  385.  * to the occurrence list. It then returns FALSE.
  386.  * If the end-of-hash table is reached, TRUE is returned.
  387.  */
  388. {        /* InsertToken */
  389.     int    HTIndex ;
  390.     
  391.     HTIndex = Hash(Token) ;
  392.     if (HTIndex == -1)
  393.         return(TRUE) ;
  394.         
  395.     if (HashTable[HTIndex].Value == NULL) {
  396.         HashTable[HTIndex].Value = Copy(Token) ;
  397.         HashTable[HTIndex].OccurList = MakeOccurrence() ;
  398.     }
  399.     else
  400.         AddOccurrence(HashTable[HTIndex].OccurList) ;
  401.         
  402.     return(FALSE) ;
  403. }        /* InsertToken */
  404.     
  405. /*==========================================================*/
  406. /*        *** IsStartingLetter() ***                            */
  407. /*==========================================================*/
  408. BOOL     IsStartingLetter(Ch, Ch2)
  409. char    Ch, Ch2 ;
  410. /* IsStartingLetter returns TRUE if Ch is a valid character to
  411.  * begin a C token.
  412.  */
  413. {        /* IsStartingLetter */
  414.     return (((isalpha(Ch) || Ch == '_') &&
  415.         (!isdigit(Ch2))) ? TRUE : FALSE) ;
  416. }        /* IsStartingLetter */
  417.     
  418. /*==========================================================*/
  419. /*        *** IsTokenLetter() ***                                */
  420. /*==========================================================*/
  421. BOOL     IsTokenLetter(Ch)
  422. char    Ch ;
  423. /* IsTokenLetter returns TRUE if Ch is a valid character
  424.  * inside a C token.
  425.  */
  426. {        /* IsTokenLetter */
  427.     return ((isalpha(Ch) || isdigit(Ch) || Ch == '_') ? TRUE : FALSE) ;
  428. }        /* IsTokenLetter */
  429.     
  430. /*==========================================================*/
  431. /*        *** MakeOccurrence() ***                            */
  432. /*==========================================================*/
  433. RefPtr    MakeOccurrence()
  434. /* MakeOccurrence creates the first entry of the line occurrence
  435.  * list. It creates the next node in the list, inserts CurLineNo
  436.  * and sets Link to NULL in preparation for the next entry.
  437.  */
  438. {        /* MakeOccurrence */
  439.     RefPtr    NewNode ;
  440.     
  441.     if ((NewNode = (RefPtr)malloc(sizeof(RefType))) == NULL) {
  442.         fprintf(stderr,"Out of Memory in MakeOccurrence.\n") ;
  443.         exit(0) ;
  444.     }
  445.     NewNode->Reference = CurLineNo ;
  446.     NewNode->Link = (RefPtr)NULL ;
  447.     
  448.     return (NewNode) ;
  449. }        /* MakeOccurrence */
  450.  
  451. /*==========================================================*/
  452. /*        *** NameCompare() ***                                */
  453. /*==========================================================*/
  454. int        NameCompare(First,Second)
  455. int        First ;
  456. int        Second ;
  457. /* NameCompare compares two entries in HashTable referenced
  458.  * by the indices First and Second. It returns FIRSTLESS if
  459.  * First < Second; EQUALS if they are equal;
  460.  * and FIRSTGREATER if First > Second.
  461.  */
  462. {        /* NameCompare */
  463.     /* If the first entry has no value, the first is less.
  464.      */
  465.     if (HashTable[First].Value == NULL)
  466.         return (FIRSTLESS) ;
  467.     
  468.     /* Then if the second has no value, the first is greater.
  469.      */
  470.     if (HashTable[Second].Value == NULL)
  471.         return (FIRSTGREATER) ;
  472.         
  473.     /* Otherwise return the comparison from strcmp.
  474.      */
  475.     return (strcmp(HashTable[First].Value, HashTable[Second].Value)) ;
  476. }        /* NameCompare */
  477.  
  478. /*==========================================================*/
  479. /*        *** PrintTable() ***                                */
  480. /*==========================================================*/
  481. VOID    PrintTable()
  482. /* PrintTable prints the list of identifiers and line occurrences.
  483.  */
  484. {        /* PrintTable */
  485.     RefPtr        ListPtr ;
  486.     int            NumOnLine ;
  487.     int            TokenCounter ;
  488.     
  489.     for (TokenCounter = 0 ; TokenCounter < HTSIZE ;
  490.             TokenCounter++) {
  491.         if (HashTable[TokenCounter].Value) {
  492.             printf("\n%-20s    ",HashTable[TokenCounter].Value) ;
  493.             for (ListPtr = HashTable[TokenCounter].OccurList, NumOnLine = 0;
  494.                     ListPtr != NULL;
  495.                     ListPtr = ListPtr->Link, NumOnLine++ ) {
  496.                 if (NumOnLine == 10) {
  497.                     printf("\n                        ") ;
  498.                     NumOnLine = 0 ;
  499.                 }
  500.                 printf("%3d  ", ListPtr->Reference) ;
  501.             }
  502.         }
  503.     }
  504.     printf("\n") ;
  505. }        /* PrintTable */
  506.  
  507. /*==========================================================*/
  508. /*        *** SortTokens() ***                                */
  509. /*==========================================================*/
  510. VOID    SortTokens(SortNumber)
  511. int        SortNumber ;
  512. /* SortTokens sorts the tokens into alphabetical order
  513.  * using a shell sort.
  514.  */
  515. {        /* SortTokens */
  516.     TokenType    Exchange ;
  517.     int            BaseCounter ;
  518.     int            CurCounter ;
  519.     int            CurGapCounter ;
  520.     int            Gap ;
  521.     int            LastInBuf ;
  522.     
  523.     LastInBuf = SortNumber ;
  524.     /* Look through all Gaps starting with a gap half the
  525.      * size of the list. Each time reduce the size of the gap
  526.      * by dividing by two.
  527.      */
  528.     for (Gap = LastInBuf / 2; Gap > 0; Gap /= 2)
  529.     
  530.     /* BaseCounter moves between the Gap-th element and
  531.      * the last element in the list. The sort using the
  532.      * current Gap runs until 1 is the LastInBuf-th
  533.      * element in the list.
  534.      */
  535.     for (BaseCounter = Gap; BaseCounter < LastInBuf; BaseCounter++)
  536.     
  537.     /* For a BaseCounter, we compare the CurCounter-th and
  538.      * the CurGapCounter-th elements in the list. CurCounter
  539.      * and CurGapCounter are always separated by Gap.
  540.      */
  541.     for (CurCounter = BaseCounter - Gap; CurCounter >= 0; CurCounter -= Gap) {
  542.         CurGapCounter = CurCounter + Gap ;
  543.         
  544.         /* If the two elements compare correctly, stop.
  545.          */
  546.         if (NameCompare(CurCounter, CurGapCounter) < EQUALS)
  547.             break;
  548.             
  549.         /* Otherwise, exchange the elements.
  550.          */
  551.         Exchange.Value = HashTable[CurCounter].Value ;
  552.         Exchange.OccurList = HashTable[CurCounter].OccurList ;
  553.         HashTable[CurCounter].Value = HashTable[CurGapCounter].Value ;
  554.         HashTable[CurCounter].OccurList = HashTable[CurGapCounter].OccurList ;
  555.         HashTable[CurGapCounter].Value = Exchange.Value ;
  556.         HashTable[CurGapCounter].OccurList = Exchange.OccurList ;
  557.     }
  558. }        /* SortTokens */
  559.  
  560. /*==========================================================*/
  561. /*        *** TransformID() ***                                */
  562. /*==========================================================*/
  563. int     TransformId(Word)
  564. char    Word[] ;
  565. /* Converts an identifier into an integer within the index
  566.  * range of HashTable.  A polynomial is generated and reduced
  567.  * modulo HTSIZE to produce this number.
  568.  */
  569. {        /* TransformId */
  570.     int            Term = 0 ;
  571.     int            WordIndex ;
  572.     
  573.     for (WordIndex = strlen(Word)-1 ; (WordIndex >= 0) ; WordIndex--)
  574.         Term = (257*Term) + Word[ WordIndex ] ;
  575.         
  576.     Term = (Term < 0 ) ? -Term : Term ;
  577.     return(Term % HTSIZE) ;
  578. }        /* TransformId */